#include<stdio.h>
#include<malloc.h>
#include<string.h>

//3.1 图结构体实现
#define NAMESIZE 20                  //名称允许长度
typedef char NODE[NAMESIZE];         //节点名称类型
typedef struct NEIGHBORNODE          //节点类型
{
    NODE node;                       //节点
    struct NEIGHBORNODE *next;       //邻近节点
}NEIGHBORNODE,*NEIGHBOR;             //相邻节点类型【*NEIGHBOR和下文中*PATH均为指向NEIGHBORNODE的指针】

typedef struct ANODE                 //节点类型
{
    NODE node;                       //节点
    NEIGHBOR adjacents;              //邻近节点
}ANYNODE;                            //节点类型【将ANODE重命名为ANYNODE】

typedef struct GRAPHNODE             //图的节点的存储类型
{
    ANYNODE node;                    //节点
    struct GRAPHNODE *next;          //其他节点
}GRAPHNODE,*GRAPH;                   //图类型【*GRAPH为指向GRAPHNODE的指针】

typedef struct NEIGHBORNODE *PATH;   //路径类型

typedef struct Paths                 //路径集合类型
{
    PATH path;                       //一条路径
    struct Paths *next;              //下一条路径
}Paths,*PATHS;                       //路径集合类型【*PATHS为指向PATH的指针】

//3.2 图存储实现

/*
//3.2.1 通用比较函数
int Equal(NODE n1,NODE n2, int *fun())
{
    return (int)fun(n1,n2);
}//判断图的两个节点是否相同，若相同则为1，否则则为0

//3.2.2 通用赋值函数
void Set (NODE n1,NODE n2,void *fun())
{
    fun(n1,n2);
}
*/

//3.2.3 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br,NODE node)        //Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b,pb;                                  //相邻节点
    b=(NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //动态开辟一个相邻节点
    //Set(b->node,node,node,SteValue);             //【下面两行是类型为str时的情况，其他类比】
    strcpy(b->node,node);
    b->next=NULL;
    if(br==NULL)                                    //没有相邻节点的情况
    {
        br=b;                                       //node就是第一个邻居
    }
    else                                            //有相邻节点的情况
    {
        pb=br;                                      //node就是最后一个相邻节点【值在b中，头插入】
        while(pb->next)   pb=pb->next;
        pb->next=b;
    }
    return br;                                      //返回相邻节点【指针】
}

//3.2.4 双亲与子节点关系的构建
GRAPH Form_Pa_Ch(NODE pa,NEIGHBOR br)                 //将相邻节点(所有子节点)链接到双亲节点中，构成一个子树
{
    GRAPH graph;
    graph=(GRAPH)malloc(sizeof(struct GRAPHNODE));   //创建双亲节点
    //Set(parent->node.node,pa,Setvalue)
    strcpy(graph->node.node,pa);
    graph->next=NULL;
    graph->node.adjacents=br;                        //相邻节点与双亲节点构成子图
    return graph;                                    //返回带相邻节点的双亲结点，即子图
}

//3.2.5 将带子节点的双亲节点加入到图中
GRAPH Add_A_Sub_Graph(GRAPH graph,GRAPH subgraph) //将双亲结点加入到图中
{
    GRAPH t=graph;                        //临时图
    if(graph==NULL)                       //图不存在
    {
        graph=subgraph;                   //带子节点的双亲节点即为图
    }
    else                                  //图存在
    {
        while(t->next)  t=t->next;
        t->next=subgraph;                 //带子节点的双亲节点加入到图的最后
    }
    return graph;                         //返回图指针
}//graph是链式队列，通过上述程序实现子图subgraph(相邻结点)进队列过程

//3.2.6 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br)  //回收相邻节点空间
{
    NEIGHBOR br1=br;                 //临时相邻变量
    while(br)                        //【遍历相邻节点】
    {
        br1=br;
        br=br->next;                //【挨个变量赋给临时指针】
        free(br1);                  //回收单元
        return br;
    }
    return br;                      //返回NULL
}

//3.2.7 清空图并回收数据单元
GRAPH ClearGraph(GRAPH graph)
{
    GRAPH graph1=graph;              //临时图
    while(graph)                     //【遍历双亲节点】
    {
        graph1=graph;
        graph=graph->next;          //【挨个变量赋给临时指针】
        free(graph1);               //回收单元
    }
    return graph;
}//在程序运行结束前需要动态回收动态开辟的数据单元
//以上两个程序实际上是出队列过程，只是没有返回值

//3.2.8 字符数值转换
//把字符串的字符'/'转换为转义字符'\0'(字符串结束标志)，故需要在字符串数组中存放多个节点名称(相邻节点)的字符串
void CreateStr(char *neighborset)  //字符数组转换为多个字符串
{
    char *c=neighborset;           //临时字符串
    while(*c)
    {
        if(*c=='/')  *c='\0';     //插入字符串结束标志
        c++;
    }
    c++;
    *c='\0';                      //多一个结束标记
}

//3.2.9 字符数组建立相邻关系
//把字符串数组中的多个相邻节点节点名称建立成图的相邻节点群(链表)
NEIGHBOR CreateNeighbors(NEIGHBOR neighbors,char *neighborset)   //若干个节点构成相邻节点
{
    char *p=neighborset;                                         //多个节点，分隔符'/'
    NODE node;
    CreateStr(neighborset);                                      //变成多个字符串
    while(*p)
    {
        //Set(Node,p,setvalue);
        strcpy(node,p);
        neighbors=Add_A_Adjacents(neighbors,node);           //加入相邻关系中
        p+=strlen(node)+1;                                  //下一个节点
    }
    return neighbors;                                        //返回相邻节点链表
}

//3.2.10 根据图文件建立图
//图文件为txt文件，其记录格式为单数行为双亲节点，偶数行为子节点，用字符'/'分隔符分开
GRAPH CreateGraph(GRAPH graph,char *filename)               //从文件创建图
{
    GRAPH subgraph;
    NEIGHBOR adjacents;
    FILE *fp;
    char neighbors[200],neighborset[5000];
    fp=fopen(filename,"r");
    while(!feof(fp))                                        //文件中是否还存在图的节点名称
    {
        fscanf(fp,"%s",neighbors);                          //读入选中节点
        fscanf(fp,"%s",neighborset);                        //读入若干相邻节点(子节点)，分隔符'/'
        adjacents=NULL;
        adjacents=CreateNeighbors(adjacents,neighborset);    //构建双亲节点
        subgraph=Form_Pa_Ch(neighbors,adjacents);            //构建子图
        graph=Add_A_Sub_Graph(graph,subgraph);               //图中加入子图
    }
    fclose(fp);                                              //关闭文件
    return graph;                                            //返回所建的图
}

#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int STATUS;                         //定义状态类型，表示“真”或“假”
typedef struct Paths *STACK;                //定义堆栈类型，实际上也是节点链表【相邻节点链表】

//3.3 图可复用代码部分
//3.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
NEIGHBOR CopyNeighbors(NEIGHBOR adjacents)                       //节点集复制
{
    NEIGHBOR copynode,lastnode,head=NULL;                        //没有子节点
    while(adjacents)
    {
        copynode=(NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        //Set(copynode->node,cildren->node,SetValue);
        strcpy(copynode->node,adjacents->node);                  //复制节点
        copynode->next=NULL;
        if(head==NULL)
        {
            head=copynode;                                       //第1个节点
        }
        else
        {
            lastnode->next=copynode;                             //非第1个节点：建立链接，复制子节点集
        }
        lastnode=copynode;
        adjacents=adjacents->next;                               //下一个子节点
    }
    return head;                                                 //返回头节点指针
}

//3.3.2 复制路径和路径集合
PATH CopyPath(PATH path)                               //复制一条路径，返回新路径
{
    PATH tempath;
    tempath=(PATH)CopyNeighbors((NEIGHBOR)path);       //路径与邻居节点集合相同
    return tempath;
}

PATHS CopyPaths(PATHS paths)                     //复制路径集合
{
    PATHS copynode,lastnode,head=NULL;
    while(paths)                                 //路径集合不为空
    {
        copynode=(PATHS)malloc(sizeof(Paths));   //路径节点
        copynode->path=CopyPath(paths->path);    //复制一条路径
        copynode->next=NULL;                     //复制路径初始化
        if(head==NULL)                           //第1条路径
        {
            head=copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next=copynode;
        }
        lastnode=copynode;                       //加入路径集合
        paths=paths->next;
    }
    return head;
}

//3.3.3 节点加入路径
PATH Add_A_Node_To_Path(NODE node,PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p=(NEIGHBOR)malloc(sizeof(NEIGHBORNODE));
    //Set(p->node,node,SetValue)
    strcpy(p->node,node);                     //等价，赋值
    if(path==NULL)                            //第1个节点
    {
        p->next=NULL;
    }
    else                                      //非第1个节点
    {
        p->next=path;                         //加入到路径头部
    }
    path=p;                                   //路径倒序加入
    return path;                              //返回路径头部
}

//3.3.4 路径加入路径集合
PATHS Add_A_Path_To_Paths(PATH path,PATHS paths) //路径加入到路径集合中
{
    PATH copypath;
    PATHS ps=NULL,p;
    if(path==NULL)   return paths;                //没有路径
    copypath=CopyPath(path);                      //复制路径
    ps=(PATHS)malloc(sizeof(Paths));              //开辟路径集合节点
    ps->path=copypath;                            //复制的路径置入
    ps->next=NULL;
    if(paths==NULL)                               //路径集合为空
    {
        paths=ps;
    }
    else                                          //路径集合为非空，新路径节点放置最后
    {
        p=paths;
        while(p->next) p=p->next;
        p->next=ps;
    }
    return paths;
}

//3.3.5 路径进栈和所有节点进栈
PATHS Push_A_Path(PATHS stack,PATH path)     //一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    PATHS st;
    tempath=CopyPath(path);                            //复制节点
    st=(PATHS)malloc(sizeof(Paths));                   //路径节点
    st->path=tempath;                                  //置路径于栈中
    if(stack==NULL)                                    //第1条路径
    {
        st->next=stack;
    }
    else                                               //非第1条路径，已有路径
    {
        st->next=stack;
    }
    stack=st;
    return stack;
}

PATHS PushPaths(PATHS stack,PATHS paths)  //所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS p,head;
    head=CopyPaths(paths);                           //复制路径集合
    p=head;
    if(p!=NULL)                                      //逐一加入栈中
    {
        while(p->next) p=p->next;
        p->next=stack;
        stack=head;
    }
    return stack;
}

//3.3.6 回收栈、回收路径和回收路径集合
STACK ClearStack(STACK stack)              //回收栈空间
{
    stack=(STACK)ClearNeighbors((NEIGHBOR)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path=(PATH)ClearNeighbors((NEIGHBOR)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS ClearPaths(PATHS paths)               //回收路径集合空间
{
    PATHS paths1=paths;
    while(paths)                              //所有路径
    {
        paths1=paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths=paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//3.3.7 出栈与节点
PATHS Pop_A_Node(STACK stack,NODE node,PATH *path)  //出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    PATHS p=stack;
    PATH tempath;
    if(p!=NULL)
    {
        tempath=p->path;                                //一条路径
        //Set(node,tempath->node,SetValue);
        strcpy(node,tempath->node);                     //获取节点
        *path=CopyPath(tempath);                         //获取路径
        stack=p->next;                                  //栈顶变化
        free(p);                                        //删除路径 
    }
    return stack;                                       //返回栈顶
}

//3.3.8 扩展节点集
NEIGHBOR ExpandNodes(GRAPH tree,NODE pa)              //由节点获取所有子节点
{
    NEIGHBOR children=NULL;                           //孩子节点
    GRAPH t=tree;                                     //树
    while(t)                                          //节点不为空
    {
        //if(Equal(t->node.node,pa,EqualFun)==0)
        if(strcmp(t->node.node,pa)==0)              //找到分支节点
        {
            children=CopyNeighbors(t->node.adjacents);
            break;
        }
        t=t->next;                                  //下一个双亲结点
    }
    return children;
}

//3.3.9 路径倒叙与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num=0,i;
    NODE *nodes;
    PATH p=path;
    while(p)                                //统计路径节点的个数
    {
        p=p->next;
        num++;
    }
    nodes=(NODE *)malloc(num*sizeof(NODE)); //开辟一维数组
    for(i=0,p=path;p;p=p->next,i++)         //读取路径节点置于数组中
    {
        //Set(nodes[i],p->node,SetValue);
        strcpy(nodes[i],p->node);
    }
    for(i=num-1,p=path;p;p=p->next,i--)     //数组数据倒序置于路径中
    {
        //Set(p->node,nodes[i],SetValue);
        strcpy(p->node,nodes[i]);
    }
    free(nodes);                            //回收数组空间
}

void PriPath(PATH path)                     //显示路径
{
    while(path!=NULL)
    {
        if(path->next->node!=NULL)  printf("%s->",path->node);
        else                        printf("%s",path->node);
        path=path->next;
    }
    printf("\n");
    //priNeighbors((NEIGHBOR)path);             //路径与兄弟节点集合形式相同
}

//3.4 图求解路径实现
//3.4.1 判断节点是否在路径中
STATUS IsInPath(NODE node,PATH path)                      //判断节点是否在路径中并返回真或假
{
    PATH p=path;
    STATUS flag=FALSE;                                    //节点是否在路径中的标识
    while(p)
    {
        //if(Equal(node,p->node,EqualFun)==0)
        if(strcmp(node,p->node)==0)                       //node在路径中
        {
            flag=TRUE;
            break;
        }
        else                                              //node不在路径中
        {
            p=p->next;
        }
    }
    return flag;                                          //返回真/假
}

//3.4.2 删除在路径中的节点
NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents,PATH path)    //从节点集合adjacents中删除节点在路径path中的节点
{
    NEIGHBOR n1=adjacents,n2;
    STATUS flag=FALSE;
    while(n1)                                              //遍历节点集合中的每个节点
    {
        flag=IsInPath(n1->node,path);                      //节点是否在路径中
        if(flag==TRUE)
        {
            if(n1==adjacents)                              //待删除节点位于第一个
            {
                adjacents=n1->next;                        //下一个节点
                free(n1);                                  //删除当前节点
                n1=adjacents;                              //其他节点
            }
            else                                           //待删除节点不在第一个
            {
                n2->next=n1->next;                         //NULL
                free(n1);                                  //删除当前节点
                n1=n2->next;                               //NULL
            }
        }
        else
        {
            n2=n1;                                          //下一个节点
            n1=n1->next;
        }
    }
    return adjacents;
}

//3.4.3  相邻节点形成路径合集
PATHS FromPathsFromNodes(NEIGHBOR adjacents,PATH path,PATHS paths)   //节点集合中的每个节点（不在路径中）挨个加入路径，依次形成路径集合
{
    PATH tempath;
    adjacents=DeleteNodeInPath(adjacents,path);           //删除构成回路的节点
    while(adjacents)                                      //所有不构成回路的节点
    {
        tempath=CopyPath(path);                              //复制路径
        tempath=Add_A_Node_To_Path(adjacents->node,tempath); //在路径中加入一个节点
        paths=Add_A_Path_To_Paths(tempath,paths);            //新路径加入路径集合
        adjacents=adjacents->next;                           //下一个节点
    }
    return(paths);                                        //返回路径集合
}

//3.4.4 路径搜索
STATUS SearchPath(GRAPH graph,NODE start,NODE end,PATH *path)   //判断节点是否在图中，并获取路径
{
    NODE node;
    NEIGHBOR adjacents;
    STACK stack=NULL;
    STATUS flag=FALSE;
    PATH tempath=NULL;
    PATHS paths=NULL;
    if(graph==NULL)   return flag;                             //图为空
    tempath=Add_A_Node_To_Path(start,tempath);                 //初始节点形成路径
    stack=Push_A_Path(stack,tempath);                          //路径进栈
    while(stack)                                               //任意一条路径
    {
        tempath=ClearPath(tempath);                            //清空路径
        stack=Pop_A_Node(stack,node,&tempath);                 //出栈
        //if(Equal(end,node,EqualFun)==0)
        if(strcmp(end,node)==0)                                //目标节点
        {
            flag=TRUE;                                         //找到目标节点
            *path=CopyPath(tempath);                           //获取路径
            break;
        }
        adjacents=ExpandNodes(graph,node);                     //相邻的所有节点
        paths=FromPathsFromNodes(adjacents,tempath,paths);     //形成不带回路的路径集合
        stack=PushPaths(stack,paths);                          //所有路径进栈
        paths=ClearPaths(paths);                               //回收所有路径
    }
    ClearStack(stack);                                         //清空堆栈
    return(flag);
}

//TAG:主程序入口1:DFS常规
//3.4.M 搜索路径部分主程序
//void PathSolve()
/*
int main()
{
    NODE start,end;                                                //起始节点、目标节点
    PATH path=NULL;                                                //路径
    STATUS flag;                                                   //节点是否在图中
    GRAPH graph=NULL;                                              //图
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Chapter3.txt";//图文件
    graph=CreateGraph(graph,filename);                             //建立图存储结构
    printf("The Start Node:");
    scanf("%s",start);                                             //输入任一起点节点名
    printf("The End Node:");
    scanf("%s",end);                                               //输入任一终点目标节点名
    flag=SearchPath(graph,start,end,&path);                        //节点start到end的路径 
    printf("Search %s from %s,Status=%d\n",end,start,flag);        //显示状态
    printf("Path=");
    RevPath(path);                                                 //路径倒序
    PriPath(path);                                                 //显示路径
    printf("===============\n");
    //ClearPath(path); 
    ClearGraph(graph);                                             //清空图存储单元
}
*/

//3.5.1 给定节点的子图
GRAPH GetSubGraph(GRAPH graph,NODE node)                         //由给定节点获取所有子节点（子图），即子图指针
{
    GRAPH subgraph=graph; 
    while(subgraph)                                              //遍历图节点
    {
        if(strcmp(subgraph->node.node,node)==0)   break;         //找到图节点
        //if(Equal(subgraph->node.node,node,EqualFun)==0) break;
        else subgraph=subgraph->next;
    }
    return subgraph;                                             //得到子图
}

//3.5.2 搜索子图生成路径
STATUS SearchSubGraphDFS(GRAPH graph,GRAPH subgraph,NODE end,PATH *path,PATH *searchpath)
//判断节点是否在图中，深度优先搜索，生成路径
{
    GRAPH subsubgraph;                                                      //子图的子图（图的给定节点）
    NEIGHBOR adjacents;                                                     //所有子节点
    STATUS flag=FALSE;                                                      //是否能从子图的子图中搜索到目标节点
    if(subgraph==NULL)                                                      //子图为空图
    {
        *path=NULL;                                                         //路径不存在（空路径）
        *searchpath=NULL;                                                   //搜索路径不存在（空路径）
        return flag;
    }
    if(strcmp(subgraph->node.node,end)==0)                                  //子图给定的节点就是目标节点
    {
        flag=TRUE;
        *searchpath=Add_A_Node_To_Path(end,*searchpath);                    //将目标节点、加入到搜索路径中
        //*path=Add_A_Node_To_Path(end,*path);【修复代码：中间路径重复输出】                                //将目标节点加入到路径中
    }
    else if(IsInPath(subgraph->node.node,*searchpath)==FALSE)               //生成搜索路径，收集所有判断过的节点（搜索路径不重复）
    {
        *searchpath=Add_A_Node_To_Path(subgraph->node.node,*searchpath);     
        adjacents=subgraph->node.adjacents;                                 //所有相邻节点
        while(adjacents)                                                    //依次遍历所有相邻节点
        {
            if(IsInPath(adjacents->node,*searchpath)==FALSE)                //未判断相邻节点
            {
                subsubgraph=GetSubGraph(graph,adjacents->node);             //相邻节点的子图
                flag=SearchSubGraphDFS(graph,subsubgraph,end,path,searchpath); //搜索子图的子图
                if(flag==TRUE)                                              //子图的目标节点存在
                {
                    *path=Add_A_Node_To_Path(adjacents->node,*path);        //相邻节点加入路径
                    break;                                                  //找到目标节点，无需再找
                }
            }
            adjacents=adjacents->next;                                      //搜索其他相邻节点
        }
    }
    return flag;                                                            //目标节点的存在性
}

//3.5.3 基于递归的搜索图生成路径
STATUS SearchPathDFSRe(GRAPH graph,NODE start,NODE end,PATH *path)              //判断节点是否在图中，深度优先搜索，生成路径
{
    GRAPH subgraph;                                                        //子图（给定节点）
    STATUS flag;                                                           //目标是否存在标识
    PATH searchpath=NULL;                                                  //搜索路径，表示已判断过的路径
    subgraph=GetSubGraph(graph,start);                                     //子图
    if(subgraph)  flag=SearchSubGraphDFS(graph,subgraph,end,path,&searchpath);//搜索
    //if(flag==TRUE)  *path=Add_A_Node_To_Path(start,*path);                 //路径存在，将初始节点加入到路径中
    printf("Search Path="); 
    RevPath(searchpath);
    PriPath(searchpath);                                                   //显示搜索路径
    ClearPath(searchpath);                                                 //清空搜索路径
    return flag;                                                           //路径的存在性

}

//TAG:主程序入口2:DFS递归
//3.5.M 搜索路径部分主程序（递归DFS）
//void PathSolveDFSRe()
/*
int main()
{
    NODE start,end;
    PATH path=NULL;
    STATUS flag;
    GRAPH graph=NULL;
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Chapter2.txt";
    graph=CreateGraph(graph,filename);
    printf("The Start Node:");
    scanf("%s",start);
    printf("The End Node:");
    scanf("%s",end);
    flag=SearchPathDFSRe(graph,start,end,&path);
    if(flag==1) path=Add_A_Node_To_Path(start,path); //【修复代码：没有头节点start的问题】
    printf("===============\n");
    printf("Search %s from %s,Status=%d\n",end,start,flag);
    printf("Path=");
    //RevPath(path);【修复代码：递归的为正序输出，无需路径倒序】
    PriPath(path);
    printf("===============\n");
    ClearPath(path); 
    ClearGraph(graph);
}
*/

//3.6.1 判断节点的存在性
STATUS IsInAdjacents(NODE node,NEIGHBOR adjacents)   //判断节点是否在节点集合中
{
    PATH path=(PATH)adjacents;                       //节点集合与路径节点存储结构相同
    return IsInPath(node,path);                      //节点是否在路径中，复用函数IsInPath
}

//3.6.2  路径定位
PATH LocatePath(NODE node,PATHS paths)               //根据节点从路径集合中获取路径
{
    PATH path=NULL;                                  //路径
    while(paths)                                     //遍历路径集合
    {
        if(strcmp(paths->path->node,node)==0)        //路径头节点与该节点相同
        //if(Equal(paths->path->node,node,EqualFun)==0)
        {
            path=paths->path;                        //找到路径
            break;
        }
        paths=paths->next;                            //继续查找
    }
    return path;                                      //返回路径
}

//3.6.3 删除路径
PATHS DelPathFromPaths(PATHS paths,PATH path)         //从路径集合中删除路径
{
    PATHS ps1=paths,ps2;
    if(paths==NULL||path==NULL)  return NULL;         //路径与路径集合不存在
    while(ps1->path!=path)                            //在路径集合中查找路径
    {
        ps2=ps1;
        ps1=ps1->next;
    }
    if(ps1!=NULL)                                     //找到路径
    {
        if(paths=ps1)                                 //路径在路径集合的头部
        {
            paths=ps1->next;
        }
        else                                          //路径不在路径集合中
        {
            ps2=ps1->next;
        }
    }
    ClearPath(ps1->path);                             //清空（删除）路径
    return paths;                                     //得到路径集合
}

//3.6.4 路径追加
PATHS Add_A_Path_To_Paths_BFS(PATH path,PATHS paths)  //将路径追加到路径集合中形成扩展的路径集合
{
    PATH copypath;                 
    PATHS ps=NULL,p;
    if(path==NULL)  return paths;                     //路径不存在，无须追加
    copypath=CopyPath(path);                          //复制路径
    ps=(PATHS)malloc(sizeof(Paths));                  //生成路径集合中的节点
    ps->path=copypath;
    ps->next=NULL;
    if(paths==NULL)                                   //路径集合为空
    {
        paths=ps;                                     //路径集合只有刚加入的路径
    }
    else                                              //路径集合不为空
    {
        p=paths;                                      //路径加入路径集合的尾部
        while(p->next)  p=p->next;
        p->next=ps;
    }
    return paths;                                     //得到路径集合
}

//3.6.5 生成路径集合
PATHS FormPaths(NEIGHBOR adjacents,PATH path)         //将节点集合中的每个节点分别加入路径
{
    PATH pt;
    PATHS paths=NULL;                                 //初始化路径集合
    while(adjacents)
    {
        pt=CopyPath(path);                            //复制路径
        pt=Add_A_Node_To_Path(adjacents->node,pt);    //在路径中加入节点，形成新路径
        paths=Add_A_Path_To_Paths_BFS(pt,paths);      //新路径加入路径集合
        adjacents=adjacents->next;                    //下一个节点
    }
    return paths;                                     //得到路径集合
}

//3.6.6 合并路径集合                                   
PATHS UnionPaths(PATHS paths1,PATHS paths)            //路径集合合并，形成新的路径集合
{
    PATHS ps=paths1;                                  //路径集合
    while(paths)                                      //路径集合不为空（所有路径）
    {
        ps=Add_A_Path_To_Paths_BFS(paths->path,ps);   //加入一条路径到路径集合中
        paths=paths->next;                            //下一条路径
    }
    return ps;                                        //合并后的路径集合
}

//3.6.7 合并节点集
NEIGHBOR UnionAdjacents(NEIGHBOR adjacents,NEIGHBOR alladjacents)     //节点集合合并【形成总节点集合】
{
    while(adjacents)                                                  //所有节点（节点集合不为空）
    {
        if(IsInAdjacents(adjacents->node,alladjacents)==FALSE)        //节点不在节点集合中
        {
            alladjacents=Add_A_Adjacents(alladjacents,adjacents->node);//加入节点
        }
        adjacents=adjacents->next;                                    //下一个节点
    }
    return alladjacents;                                              //合并后集合
}

//3.6.8 相差节点集
NEIGHBOR DiffAdjancents(NEIGHBOR adjacents,NEIGHBOR alladjacents)     //节点集合合并【将不在总结点集合中的点加入差节点集合】
{
    NEIGHBOR minusadjacents=NULL;                                     //新节点集合【差节点集合】
    while(adjacents)                                                  //所有节点
    {
        if(IsInAdjacents(adjacents->node,alladjacents)==FALSE)
        {
            minusadjacents=Add_A_Adjacents(minusadjacents,adjacents->node);
        }
        adjacents=adjacents->next;                                    //下一个节点
    }
    return minusadjacents;                                            //节点集合的差集
}

//3.6.9 递归搜索子图
STATUS SearchSubGraphBFS(GRAPH graph,GRAPH subgraph,NODE end,PATH *path1,PATH *searchpath,NEIGHBOR *alladjacents1,PATHS *allpaths)
//判断节点是否在图中，广度优先搜索，生成路径【递归搜索子图，生成求解路径、搜索路径和相邻节点集合】
{
    GRAPH subsubgraph;                     //子图的子图（图的给定节点）
    NEIGHBOR adjacents;                    //所有子节点
    NEIGHBOR alladjacents=*alladjacents1;  //搜索过程中的所有结点
    STATUS flag=FALSE;                     //是否能从子图中搜索到目标标识
    PATH path=NULL,locpath;                //求解路径、临时定位路径
    PATHS paths=*allpaths;                 //路径集合
    if(subgraph==NULL)                     //子图为空图
    {
        *path1=NULL;                       //路径不存在（空路径）
        *allpaths=NULL;                    //路径集合不存在
        return flag;
    }
    //if(EqualFun(subgraph->node.node,end,EqualFun)==0)
    if(strcmp(subgraph->node.node,end)==0)                                //子图的给定节点就是目标节点
    {
        flag=TRUE;                                                        //该节点是目标节点
        *path1=Add_A_Node_To_Path(subgraph->node.node,NULL);              //形成求解路径
    }
    else if(IsInPath(subgraph->node.node,*searchpath)==FALSE)             //当前节点不在搜索路径中
    {
        *searchpath=Add_A_Node_To_Path(subgraph->node.node,*searchpath);  //加入节点，形成搜索路径
        adjacents=subgraph->node.adjacents;                               //当前节点所有的相邻节点
        adjacents=DiffAdjancents(adjacents,*searchpath);                  //排除在搜索路径中的相邻节点
        if(*allpaths==NULL)                                               //刚开始搜索，路径集合为空
        {
            path=Add_A_Node_To_Path(subgraph->node.node,NULL);            //生成第一条路径
            paths=FormPaths(adjacents,path);                              //相邻节点集合与路径生成路径集合
            *allpaths=UnionPaths(*allpaths,paths);                        //路径集合合并，即收集路径集合
        }
        else                                                              //不是刚开始搜索，路径集合不为空
        {
            locpath=LocatePath(subgraph->node.node,*allpaths);            //在路径集合中找到路径     
            path=CopyPath(locpath);                                       //复制路径
            *allpaths=DelPathFromPaths(*allpaths,locpath);                //在路径集合中删除路径
            paths=FormPaths(adjacents,path);                              //相邻节点集合与路径生成路径集合
            *allpaths=UnionPaths(*allpaths,paths);                        //路径集合合并，即收集路径集合
        }
        ClearPath(path);                                                  //清除临时路径
        ClearPaths(paths);                                                //清除临时路径集合
        *alladjacents1=UnionAdjacents(adjacents,*alladjacents1);
        //合并当前相邻节点到迄今为止的所有相邻节点集合（队列操作）
        alladjacents=*alladjacents1;                                      //依次遍历所有相邻节点（取队列头节点）
        while(alladjacents)                                               //依次遍历所有相邻节点
        {
            if(IsInPath(alladjacents->node,*searchpath)==FALSE)           //相邻节点不在搜索路径中
            {
                subsubgraph=GetSubGraph(graph,alladjacents->node);        //相邻节点的子图
                flag=SearchSubGraphBFS(graph,subsubgraph,end,path1,searchpath,alladjacents1,allpaths);
                //递归搜索子图的子图
                if(flag==TRUE)                                            //子图的子图目标存在
                {
                    *path1=LocatePath(end,*allpaths);                     //从路径集合中找到路径
                    break;                                                //找到目标，无须再找
                }
            }
            alladjacents=alladjacents->next;                              //搜索其他相邻节点
        }
    }
    return flag;                                                          //目标节点的存在性
}

//3.6.10 递归路径求解
STATUS SearchPathBFSRe(GRAPH graph,NODE start,NODE end,PATH *path)
//判断节点是否在图中，广度优先搜索，生成路径【给定初始节点和目标节点得到求解路径】
{
    GRAPH subgraph;                                              //子图（给定路径）
    STATUS flag=FALSE;                                           //目标是否已存在标识
    PATH searchpath=NULL;                                        //搜索路径，表示已判断过的路径
    NEIGHBOR alladjacents=NULL;                                  //所有相邻节点（队列）
    PATHS allpaths=NULL;                                         //求解路径集合
    subgraph=GetSubGraph(graph,start);                           //子图
    if(subgraph)  flag=SearchSubGraphBFS(graph,subgraph,end,path,&searchpath,&alladjacents,&allpaths);
    //搜索
    if(flag==TRUE) searchpath=Add_A_Node_To_Path(end,searchpath); //若路径存在，则加入初始节点
    RevPath(searchpath);                                          //搜索路径倒序
    printf("Search Path=");                                       //显示搜索路径
    PriPath(searchpath);
    RevPath(*path);                                               //求解路径倒序
    ClearPath(searchpath);                                        //清空搜索路径
    ClearNeighbors(alladjacents);                                 //清空所有相邻节点集合
    return flag;                                                  //路径的存在性
}

//Tag:主程序入口3:BFS递归
//3.6.M 搜索路径部分主程序（递归BFS）
//void PathSolveBFSRe()
int main()
{
    NODE start,end;
    PATH path=NULL;
    STATUS flag;
    GRAPH graph=NULL;
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Chapter4\\Chapter4-Exercise2.txt";
    graph=CreateGraph(graph,filename);
    printf("The Start Node:");
    scanf("%s",start);
    printf("The End Node:");
    scanf("%s",end);
    flag=SearchPathBFSRe(graph,start,end,&path);
    printf("===============\n");
    printf("Search %s from %s,Status=%d\n",end,start,flag);
    printf("Path=");
    //RevPath(path);【修复代码：递归的为正序输出，无需路径倒序】
    PriPath(path);
    printf("===============\n");
    ClearPath(path); 
    ClearGraph(graph);
}